package com.liyghting.datastructurealgorithm.stack;

/**
 * 基于数组实现的栈
 * 
 * @author LiYiGuang
 * @date 2018/11/19 11:40
 */
public class StackBasedArray2 {
	private String[] items; // 数组
	private int count;// 栈中元素个数
	private int n; // 栈的大小
	// 初始化数组，申请一个大小为n的数组空间

	public StackBasedArray2(int n) {
		this.items = new String[n];
		this.n = n;
		this.count = 0;
	}

	// 改变数组容量
	public void resize(int n) {
		String[] temps = new String[n];
		int length = n > this.n ? this.n : n;
		for (int i = 0; i < length; i++) {
			temps[i] = items[i];
		}
		items = temps;
		this.n = n;
	}

	// 入栈
	public boolean push(String item) {
		if (count == n)
			resize(2 * n);
		items[count++] = item;
		return true;
	}

	// 出栈
	public String pop() {
		if (count == 0)
			return null;
		String temp = items[count - 1];
		items[count - 1] = null;
		count--;
		if (count == n / 4)
			resize(n / 2);
		return temp;
	}

	public String peek() {
		if (count == 0)
			return null;
		return items[count - 1];
	}

	public void printAll() {
		if (count == 0)
			return;
		for (int i = items.length; i > 0; i--) {
			System.out.print(items[i - 1] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		StackBasedArray2 stack = new StackBasedArray2(10);
		for (int i = 0; i < 20; i++) {
			stack.push(i + "");
		}
		stack.printAll();
		for (int i = 0; i < 15; i++) {
			stack.pop();
		}
		stack.printAll();
	}

}
